package leetcode_500;

import java.util.Arrays;

/**
 *@author 周杨
 *ReversePairs_493_ nums[j]>2*nums[i]+1 的个数
 *describe:用归并  AC 85%
 *2018年9月4日 下午3:58:29
 */
public class ReversePairs_493_ {
	/**
	 * describe:完美解 用归并 AC 85%
	 * 2018年9月4日 下午1:49:26
	 */
	public int reversePairs(int[] nums) {
        if (nums == null || nums.length <= 1) return 0;
        long[] helper = new long[nums.length];
        return mergeSort(nums, 0, nums.length - 1, helper);
    }
    
    private int mergeSort(int[] nums, int left, int right, long[] helper) {
        if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        int half1 = mergeSort(nums, left, mid, helper);
        int half2 = mergeSort(nums, mid + 1, right, helper);
        int cur = merge(nums, left, mid, right, helper);
        return half1 + half2 + cur;
    }
    
    private int merge(int[] nums, int left, int mid, int right, long[] helper) {
        for (int i = left; i <= right; i++) {
            helper[i] = nums[i];
        }        
        int ind1 = left, ind2 = mid + 1, res = 0;
        while (ind1 <= mid) {
            while (ind2 <= right && helper[ind1] > 2 * helper[ind2]) {
                ind2++;
            }
            res += ind2 - mid - 1;
            ind1++;
        }
        // merge
        ind1 = left;
        ind2 = mid + 1;
        int cur = left;
        while (ind1 <= mid && ind2 <= right) {//开始排序
            if (helper[ind1] <= helper[ind2]) {
                nums[cur++] = (int) helper[ind1++];
            } else {
                nums[cur++] = (int) helper[ind2++];
            }
        }        
        while (ind1 <= mid) {
            nums[cur++] = (int) helper[ind1++];
        }
        return res;
    }
    
    
    /**
     * describe:bit法解决 AC 17%
     * 2018年9月4日 下午3:52:02
     */
    public int reversePairs1(int[] nums) {
        int n = nums.length;
        
        // why long? 2 * nums[i] could overflow
        // why this array? need its indexes to build bit
        long[] nums2 = new long[n];
        for (int i = 0; i < n; i++) {
            nums2[i] = (long)nums[i];//复制这个数组并且为其排序
        }
        Arrays.sort(nums2);
        
        int[] bit = new int[n + 1];
        
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int curr = nums[i];
            
            int idx1 = Arrays.binarySearch(nums2, 2l * curr + 1);
            count += query(bit, (idx1 < 0 ? -(idx1 + 1) : idx1) + 1);

            int idx2 = Arrays.binarySearch(nums2, curr);
            insert(bit, (idx2 < 0 ? -(idx2 + 1) : idx2) + 1, 1);
        }
        
        return count;    
    }
    
    private int query(int[] bit, int x) {
        int res = 0;
        
        for (int i = x; i < bit.length; i += i & -i) {
            res += bit[i];
        }
        
        return res;
    }
    
    private void insert(int[] bit, int x, int val) {
        for (int i = x; i > 0; i -= i & -i) {
            bit[i] += val;
        }
    }
}
